//双端队列
#ifndef __DOUBLEENDEDQUEUE__HPP
#define __DOUBLEENDEDQUEUE__HPP

#include"VirtualQueue.hpp"

namespace NgSiuKei {

template<class TheClass>
class DoubleEndedQueue: public VirtualQueue<TheClass> {
    public:
    DoubleEndedQueue(void);
    ~DoubleEndedQueue(void);

    public:
    //清空
    void clear(void);
    //获取队头元素
    TheClass getFrontVal(void) const;
    //入队列，默认使用pushRear
    void push(const TheClass val);
    //出队列，默认使用popFront
    TheClass pop(void);
    //打印队列
    void print(void) const;

    public:
    //入队列（队头）
    void pushFront(const TheClass val);
    //入队列（队尾）
    void pushRear(const TheClass val);
    //出队列（队头）
    TheClass popFront(void);
    //出队列（队尾）
    TheClass popRear(void);

    private:
    TheClass *p;
    U_L_L frontIndex;
    U_L_L rearIndex;
};

template<class TheClass>
DoubleEndedQueue<TheClass>::DoubleEndedQueue(void): VirtualQueue<TheClass>() {
    this->p = new TheClass[MAX_SIZE];
    this->frontIndex = -1;
    this->rearIndex = -1;
}

template<class TheClass>
DoubleEndedQueue<TheClass>::~DoubleEndedQueue(void) {
    delete this->p;
}

template<class TheClass>
void DoubleEndedQueue<TheClass>::clear(void) {
    this->size = 0;
    this->frontIndex = 0;
    this->rearIndex = 0;
}

template<class TheClass>
TheClass DoubleEndedQueue<TheClass>::getFrontVal(void) const {
    if(this->isEmpty()) {
        throw EXCEPTION_IS_EMPTY;
    }
    return this->p[this->frontIndex];
}

template<class TheClass>
void DoubleEndedQueue<TheClass>::push(const TheClass val) {
    this->pushRear(val);
}

template<class TheClass>
TheClass DoubleEndedQueue<TheClass>::pop(void) {
    return this->popFront();
}

template<class TheClass>
void DoubleEndedQueue<TheClass>::print(void) const {
    cout << "打印双端队列：[ ";
    U_L_L currentIndex = this->frontIndex;
    for(U_L_L i=0; i<this->size; ++i, (currentIndex+1)%MAX_SIZE) {
        cout << this->p[currentIndex] << ' ';
    }
    cout << ']' << endl;

    // cout << "实际数组状态：["<< this->frontIndex << ':' << this->rearIndex <<"][" << this->size << "][ ";
    // for(U_L_L i=0; i<MAX_SIZE; ++i) {
    //     cout << this->p[i] << ' ';
    // }
    // cout << ']' << endl;
}

template<class TheClass>
void DoubleEndedQueue<TheClass>::pushFront(const TheClass val) {
    if(MAX_SIZE == this->size) {
        throw EXCEPTION_IS_FULL;
    }

    if(0 == this->frontIndex) {
        this->frontIndex = MAX_SIZE;
    }
    this->frontIndex--;
    this->p[this->frontIndex] = val;
    if(this->isEmpty()) {
        this->rearIndex = this->frontIndex;
    }
    this->size++;
}

template<class TheClass>
void DoubleEndedQueue<TheClass>::pushRear(const TheClass val) {
    if(MAX_SIZE == this->size) {
        throw EXCEPTION_IS_FULL;
    }

    this->rearIndex = (this->rearIndex+1)%MAX_SIZE;
    this->p[this->rearIndex] = val;
    if(this->isEmpty()) {
        this->frontIndex = this->rearIndex;
    }
    this->size++;
}

template<class TheClass>
TheClass DoubleEndedQueue<TheClass>::popFront(void) {
    if(this->isEmpty()) {
        throw EXCEPTION_IS_EMPTY;
    }

    TheClass resultVal = this->p[this->frontIndex];
    this->frontIndex = (this->frontIndex+1)%MAX_SIZE;
    this->size--;
    if(this->isEmpty()) {
        this->frontIndex = this->rearIndex;
    }
    return resultVal;
}

template<class TheClass>
TheClass DoubleEndedQueue<TheClass>::popRear(void) {
    if(this->isEmpty()) {
        throw EXCEPTION_IS_EMPTY;
    }

    TheClass resultVal = this->p[this->rearIndex];
    if(0 == this->rearIndex) {
        this->rearIndex = MAX_SIZE;
    }
    this->rearIndex--;
    this->size--;
    if(this->isEmpty()) {
        this->frontIndex = this->rearIndex;
    }
    return resultVal;
}

}

#endif